#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int a = 0, left = 0, right = 0, tmp = 0;
        vector<vector<int>> sum;

        sort(nums.begin(), nums.end());
        for (a = 0; a < nums.size() - 2; a++) {
            if (a != tmp) {

                while (nums[a] == nums[tmp] && a < nums.size() - 2) {
                    a++;
                }
            }
            left = a + 1;
            right = nums.size() - 1;

            while (left < right) {
                if (nums[left] + nums[right] + nums[a] < 0) {
                    left++;
                }
                else if (nums[left] + nums[right] + nums[a] > 0) {
                    right--;
                }
                else if (nums[left] + nums[right] + nums[a] == 0) {
                    tmp = a;
                    sum.push_back({ nums[a], nums[left], nums[right] });
                    if (nums.size() == 3) {
                        return sum;
                    }
                    do {
                        left++;
                    } while (nums[left] == nums[left - 1] &&
                        left < nums.size() - 1);
                    do {
                        right--;
                    } while (nums[right] == nums[right + 1] && right > left);
                }
            }
        }
        return sum;
    }
};